/**83. 删除排序链表中的重复元素 */
/**
 * 1. 定义两个指针
 * 2. 如果两个指针值相同，则后指针向后移动一位，同时改变前指针节点的next指向
 * 否则： 前后指针同时向后移动
 */
var deleteDuplicates = function (head) {
  if (!head || !head.next) return head;
  let pre = head, next = head.next;
  while (next) {
    if (pre.val === next.val) {
      pre.next = next.next;
    } else {
      pre = next;
    }

    next = next.next;
  }
  return head;
};
// 收获：1. 使用双指针

/**82. 删除排序链表中的重复元素 II */
// 需要比较当前节点 后面的多个节点是否相同， 81题比较当前节点和后面的节点即可
// cur后面的节点和 next后面的节点
// 1. 不相同： cur和next同时向后走一步
// 2. 相同： 
//    1. next向后走，直到走到不同的节点
//    2. 将cur的next指针指向这个节点，进行下一次循环
var deleteDuplicates = function (head) {
  if (!head || !head.next) return head;
  const ret = new ListNode(null, head);

  let cur = ret, next = head;
  while (next && next.next) {
    if (cur.next.val === next.next.val) { // 后面节点相同
      while (next && next.next && cur.next.val === next.next.val) {
        next = next.next;
      }
      // 找到下一个不同的节点了
      cur.next = next.next;
    } else {
      cur = cur.next;
    }
    next = next.next;
  }
  return ret.next;
};
// 收获：1. 虚拟头节点： 如果头节点又可能被更换，就需要用到虚拟头节点

/**92. 反转链表 II */
/**
 * 1. 找到预反转的节点的前一个节点
 * 2. 反转需要反转的部分
 * 3. 拼接链表
 */
var resvers = function (head, n) {
  if (!head || !head.next) return head;
  let pre = null, cur = head;
  while (cur && n-- > 0) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next
    // [cur.next, pre, cur] = [pre, cur, cur.next];
  }

  // 拼接剩余的节点
  head.next = cur;
  return pre;
}

var reverseBetween = function (head, left, right) {
  if (!head || !head.next) return head;
  const ret = new ListNode(null, head);
  // 查找反转的前一个节点
  const n = right - left + 1;
  let cur = ret;
  while (--left) {
    cur = cur.next;
  }

  let temp = resvers(cur.next, n);

  // 前半部分拼接后半部分
  cur.next = temp;
  return ret.next;
};

/**25. K 个一组翻转链表 */
// 每反转k个节点，指针向后走k步
var resver = function (head, n) {
  if (!head || !head.next) return head;
  // 判断是否足够k个节点
  let con = n;
  let cur = head;
  while (cur && --con) {
    cur = cur.next;
  }
  if (!cur) return head;

  // 反转k个节点
  let pre = null;
  cur = head;
  while (n--) {
    let next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  head.next = cur;
  return pre;
}
var reverseKGroup = function (head, k) {
  if (!head || k < 2) return head;
  let ret = new ListNode(-1, head);
  let cur = ret;
  while (cur) {
    const temp = resver(cur.next, k);
    cur.next = temp;

    // cur向后走k步
    let con = k;
    while (con-- && cur) {
      cur = cur.next;
    }
  }
  return ret.next;
};
// 注意：如果如惨需要被传递，就不要在程序中改变入惨，而是另赋值变量。

/**19. 删除链表的倒数第 N 个结点 */
var removeNthFromEnd = function (head, n) {
  if (!head) return head;
  let ret = new ListNode(null, head);
  let pre = ret, next = ret;
  // 后面的指针先走n步
  while (n--) {
    next = next.next;
  }

  while (next.next) {
    pre = pre.next;
    next = next.next;
  }
  // 删除目标节点
  pre.next = pre.next.next;
  return ret.next;
};

/**202. 快乐数 */
// 计算机中最大的数 2147483647 -> 1999999999 = 81 * 9 + 1 = 730
// 如果出现循环，说明有环
var getNext = function (n) {
  let ret = 0;
  while (n) {
    let num = n % 10;
    ret += num * num;
    n = (n / 10) | 0;
  }
  return ret;
}

var isHappy = function (n) {
  if (n === 1) return true;
  let pre = n, next = getNext(n);
  while (pre !== next && next !== 1) {
    pre = getNext(pre);
    next = getNext(getNext(next));
  }
  return next === 1;
};
// 收获：1.依次获取数字的每一位 2.位运算

/**860 柠檬水找零 */
// 有10元的先找10元的
var lemonadeChange = function (bills) {
  let five = 0;
  let ten = 0;
  for (let i = 0; i < bills.length; i++) {
    switch (bills[i]) {
      case 5:
        five++;
        break;
      case 10:
        if (five < 1) return false;
        five--;
        ten++;
        break;
      case 20:
        if (five < 1) return false;
        if (ten > 0) {
          if (five === 0) return false;
          ten--;
          five--;
        } else {
          if (five < 3) return false;
          five -= 3;
        }
        break;
    }
  }
  return true;
};

/**969 煎饼排序 */
var reverse = function (arr, result) {
  if (arr.length === 1) return;
  let arr1 = []; // 去除数组最大的元素后的数组
  for (let i = 0; i < arr.length; i++) { //  arr.length就是最大的数字
    if (arr[i] === arr.length) {
      result.push(i + 1);
      // 滤掉了最大元素
      arr1 = arr.slice(0, i).reverse().concat(arr.slice(i + 1));
      break;
    };
  }
  result.push(arr.length)
  reverse(arr1.reverse(), result);
}
var pancakeSort = function (arr) {
  var result = [];
  reverse(arr, result);
  return result;
};

var reserveArr = function (arr) {
  let i = 0, j = arr.length - 1;
  while (j > i) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++;
    j--;
  }
  return arr;
}


/**859. 亲密字符串 */
var buddyStrings = function (a, b) {
  if (a.length !== b.length) return false;
  if (a === b) return a.length > new Set(a).size;
  let temp = [];
  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      temp.push(a[i], b[i]);
    }
  }
  return (temp.length === 4) && (temp[0] === temp[3]) && (temp[1] === temp[2])
}

let arr = [20, 12, 35, 73, 66];
console.log(reserveArr(arr));




const reverse = function (arr) {
  let i = 0, j = arr.length - 1;
  while (j > i) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++;
    j--;
  }
  return arr;
}

let arr = [1, 3, 4, 2, 6, 7, 9];
console.log(reverse(arr)); 